package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * <a href='https://leetcode.cn/problems/non-decreasing-subsequences/'>非递减子序列(Non-decreasing Subsequences)</a>
 * <p>给你一个整数数组 nums ，找出并返回所有该数组中<b>不同的</b>递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。</p>
 * <p>数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：nums = [4,6,7,7]
 *      输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
 *
 *  示例 2：
 *      输入：nums = [4,4,3,2,1]
 *      输出：[[4,4]]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= nums.length <= 15</li>
 *     <li>-100 <= nums[i] <= 100</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/13 14:05
 */
public class LC0491NonDecreasingSubsequences_M {
    static class Solution {
        public List<List<Integer>> findSubsequences(int[] nums) {
            List<List<Integer>> resList = new ArrayList<>();
            //backtracking(nums, 0, new ArrayList<>(), resList);
            backtracking(nums, 0, Integer.MIN_VALUE, new ArrayList<>(), resList);
            return resList;
        }

        /**
         * 使用set去重
         */
        private void backtracking(int[] nums, int startIdx, List<Integer> path, List<List<Integer>> resList) {
            if (path.size() >= 2) {
                resList.add(new ArrayList<>(path));
            }
            Set<Integer> visited = new HashSet<>();
            for (int currIdx = startIdx; currIdx < nums.length; currIdx++) {
                // 去重
                if (visited.contains(nums[currIdx])) {
                    continue;
                }
                // 非递减
                if (path.isEmpty() || path.get(path.size() - 1) <= nums[currIdx]) {
                    path.add(nums[currIdx]);
                    visited.add(nums[currIdx]);
                    backtracking(nums, currIdx + 1, path, resList);
                    path.remove(path.size() - 1);
                }
            }
        }

        /**
         * 使用数组代替set去重
         */
        private void backtracking2(int[] nums, int startIdx, List<Integer> path, List<List<Integer>> resList) {
            if (path.size() >= 2) {
                resList.add(new ArrayList<>(path));
            }
            // 题目给出的数字范围是[-100,100]，可以使用数组代替set
            boolean[] visited = new boolean[201];
            for (int currIdx = startIdx; currIdx < nums.length; currIdx++) {
                int val = nums[currIdx];
                if (visited[val + 100]) {
                    continue;
                }
                // 保证结果的非递减
                if (path.size() == 0 || path.get(path.size() - 1) <= val) {
                    visited[val + 100] = true;
                    path.add(val);
                    backtracking2(nums, startIdx + 1, path, resList);
                    path.remove(path.size() - 1);
                }
            }
        }

        private void backtracking(int[] nums, int currIdx, int last, List<Integer> path, List<List<Integer>> resList) {
            if (currIdx == nums.length) {
                if (path.size() >= 2) {
                    resList.add(new ArrayList<>(path));
                }
                return;
            }
            // 能保证非递减的情况下，才可以选
            if (nums[currIdx] >= last) {
                path.add(nums[currIdx]);
                backtracking(nums, currIdx + 1, nums[currIdx], path, resList);
                path.remove(path.size() - 1);
            }
            // 去重
            if (nums[currIdx] != last) {
                backtracking(nums, currIdx + 1, last, path, resList);
            }
        }
    }
}
